package com.algorithm.lesson_04;

import java.util.LinkedList;

public class SlidingWindowMaxArray {

	/**
	 * 
	 * @param arr
	 *            窗口要遍历的数组
	 * @param w
	 *            窗口大小
	 * @return
	 */
	public static int[] getMaxWindow(int[] arr, int w) {
		if (arr == null || w < 1 || arr.length < w) {
			// 检测输入是否符合条件 1:arr非空 2:窗口大小w至少为1 3:数组大小不小于窗口大小
			return null;
		}
		// 滑动窗口遍历后得到的结果数组 大小一定为n-w+1
		int[] res = new int[arr.length - w + 1];
		// 双端队列用来保存窗口内最大值的下标
		LinkedList<Integer> qmax = new LinkedList<>();
		// 标记已写入结果数组的最大值数
		int index = 0;

		// 元素下标:0 1 2 3 4 5 6 7
		// 元素的值:4 3 5 4 3 3 6 7
		// 当前队列:[]
		// i:0	a[0]=4	Empty	[4]
		// i:1	a[1]=3	last:4<=3(NO)	[4,3]
		// i:2	a[2]=5	last:3<=5(poll) last:4<5(poll) [2]([5]) i>=2(符合窗口长度最小下标)-->res[5]
		// i:3	a[3]=4	last:5<=4(NO)	invalidIndex:0	[2,3]([5,4]) -->res[5,5]
		// i:4	a[4]=3	last:4<=3(NO)	invalidIndex:1	[2,3,4]([5,4,3]) -->res[5,5,5]
		// i:5	a[5]=3	last:3<=3(poll) invalidIndex:2	[3,5]([4,3]) -->res[5,5,5,4]
		// i:6	a[6]=6	last:3<=6(poll)	invalidIndex:3	[6]([6]) -->res[5,5,5,4,6]
		// i:7	a[7]=7	last:6<=7(poll)	invalidIndex:4	[7]([7]) -->res[5,5,5,4,6,7]

		for (int i = 0; i < arr.length; i++) {
			// 将当前检测的元素与队尾进行比较，如果队尾较小或相等则移除队列
			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
				qmax.pollLast();
			}
			// 将新检测到的元素下标添加到队列中，新添加到队列元素的下标必定是最大的，较小的已经移除
			qmax.addLast(i);
			if (qmax.peekFirst() == i - w) {
				// 判断队头元素下标是否过期，过期则移除队头
				qmax.pollFirst();
			}
			if (i >= w - 1) {
				// 当当前已检测宽度超过滑动窗口大小时，将队列的头部写入到结果数组中
				res[index++] = arr[qmax.peekFirst()];
			}
		}

		return res;
	}

	public static int[] getMinWindow(int[] arr, int w) {
		if (arr == null || w < 1 || arr.length < w) {
			return null;
		}
		LinkedList<Integer> qmin = new LinkedList<>();
		int[] res = new int[arr.length - w + 1];
		int index = 0;
		for (int i = 0; i < arr.length; i++) {
			while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[i]) {
				qmin.pollLast();
			}
			qmin.addLast(i);
			if (qmin.peekFirst() == i - w) {
				qmin.pollFirst();
			}
			if (i >= w - 1) {
				res[index++] = arr[qmin.peekFirst()];
			}
		}

		return res;
	}

	/**
	 * 打印数组
	 * 
	 * @param arr
	 */
	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}
